package ljl.alg.hot100;

public class _338_count_bits {
    
    /*
    * 3 个动态规划解法
    * 其实我的 notgood2 也用到了一些动态规划思路了
    * */
    public static class Dp3 {
    
        // 最高有效位
        /*
        从小到大找目前为止，不必当前数大的那个 2 的正数幂
        然后，当前数 1 个数等于 bits[i - 那个幂] + 1
        bits[i - 那个幂] 已知
        
        到这如果看不懂可以自杀了
        * */
        public int[] countBits1(int n) {
            int[] bits = new int[n + 1];
            int highBit = 0;
            for (int i = 1; i <= n; i++) {
                if ((i & (i - 1)) == 0) {
                    highBit = i;
                }
                bits[i] = bits[i - highBit] + 1;
            }
            return bits;
        }
    
        // 最低有效位
        /*
        对于每个数而言，它都比它除掉最低位的那个数多一个 1，如果当前下标最低位是 1 的话。
        否则数量不变！
        
        这个比上面绕一点
        * */
        public int[] countBits2(int n) {
            int[] bits = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                bits[i] = bits[i >> 1] + (1 & i);
            }
            return bits;
        }
    
        // 最低设置位
        // 每个数 1 个数，等于它消去最低位那个 1 之后的数的 1 个数 + 1
        public int[] countBits3(int n) {
            int[] bits = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                bits[i] = bits[i & (i - 1)] + 1;
            }
            return bits;
        }
    }
    
    /**
     * */
    public static class Sb {
    
        int[] res;
        int index = 1;
        public int[] countBits(int n) {
            res = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                calc(i);
            }
            return res;
        }
        
        void calc(int n) {
            int count = 0;
            int p = n;
            while(p > 0) {
                /*
                * 这有优化空间，应该用 n & (n - 1) 消一个 1
                * p &= p - 1;
                * count++;
                *
                * 这样快了很多！
                * */
                if ((p & 1) == 1) {
                    count++;
                }
                p >>= 1;
                
                // 咋看不懂这一段？
                // 是不是说 < index 的被求过值了，所以直接用结果?
                if(p < index) {
                    res[n] = count + res[p];
                    index++;
                    break;
                }
            }
        }
    }
    
    
    /**
     * 这样挺快，但是还有别的办法
     * */
    public static class NotGood {
        public int[] countBits(int n) {
            int[] res = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                res[i] = Integer.bitCount(i);
            }
            return res;
        }
    }
}
